package com.msb.平衡树;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 测试链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii
// 53min
public class 二叉树打印每层结果返回_mid {

	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
		TreeNode(int val) {
			this.val = val;
		}
	}

	// 把每层要处理的节点,专门拿个queue记下来, 然后poll取值
	// 大坑: 修改了队列, size会变的, 所以要提前记下来
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> res = new LinkedList<>();
		if (root == null) {
			return res;
		}
		Queue<TreeNode> nodes = new LinkedList<>();
		nodes.add(root);
		while (!nodes.isEmpty()) {
			List<Integer> layer = new LinkedList<>();
			int size = nodes.size();
			for (int i = 0; i < size; i++) {
				TreeNode poll = nodes.poll();
				layer.add(poll.val);
				if (poll.left != null) {
					nodes.add(poll.left);
				}
				if (poll.right != null) {
					nodes.add(poll.right);
				}
			}
			res.add(0, layer);
		}
		return res;
	}
}
